package com.tys.algorithm.advanced.code.class07;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.PriorityQueue;


/*
 * 手写加强堆
 * T一定要是非基础类型，有基础类型需要包一层
 */
public class HeapGreater<T> {
    //小根堆数组
    private ArrayList<T> heap;
    //反向索引表：key是值,value是堆数组的下标索引
    //heap=[a, b, c]
    //a->0,
    //b->1,
    //c->2
    private HashMap<T, Integer> indexMap;
    //堆大小
    private int heapSize;
    //T 的比较器
    private Comparator<? super T> comp;

    //构造函数初始化
    public HeapGreater(Comparator<? super T> c) {
        heap = new ArrayList<>();
        indexMap = new HashMap<>();
        heapSize = 0;
        comp = c;
    }

    //判断堆是否为空
    public boolean isEmpty() {
        return heapSize == 0;
    }

    //获取堆大小
    public int size() {
        return heapSize;
    }

    //判断堆中是否有指定对象
    public boolean contains(T obj) {
        return indexMap.containsKey(obj);
    }

    //获取堆顶元素
    public T peek() {
        return heap.get(0);
    }

    //元素入堆
    public void push(T obj) {
        heap.add(obj); //入堆
        indexMap.put(obj, heapSize); //同步索引,放入索引表
        heapInsert(heapSize++); //从堆底开始向上调整堆
    }

    //弹出堆顶元素
    public T pop() {
        T ans = heap.get(0); //堆顶
        swap(0, heapSize - 1); //堆尾和堆顶交换
        indexMap.remove(ans);//删除原来堆顶索引,反向索引删除
        heap.remove(--heapSize);//移除堆尾,删除堆
        heapify(0);//从堆顶开始向下调整堆，向下重新调整堆
        return ans; //返回原始堆顶元素
    }

    //非系统功能2：高效删除任意一个对象
    //最后一个堆尾元素和要删除的元素做替换
    public void remove(T obj) {
        //保存末尾对象
        T replace = heap.get(heapSize - 1);
        //保存对象索引
        int index = indexMap.get(obj);
        //从反向索引表删除，删除指定对象索引
        indexMap.remove(obj);
        //删除堆最后的对象，从堆中删除指定对象
        heap.remove(--heapSize);
        //要删除最后元素时，是否删除的是堆尾元素
        if (obj != replace) {
            //将保存的末尾对象替换到删除对象位置
            //原堆尾元素覆盖obj的位置
            heap.set(index, replace);
            //替换索引,修改原堆尾索引
            indexMap.put(replace, index);
            //重新调整末尾对象的位置,重新调整指定元素的位置
            resign(replace);
        }
    }

    //自己写的
    public void remove2(T obj) {
        int index = indexMap.get(obj);
        swap(index, heapSize - 1);
        heap.remove(--heapSize);
        heapify(index);
        indexMap.remove(obj);
    }

    //非系统功能1：调整指定元素在堆中位置,给定一个对象，整个堆调有序
    //O(logN)
    public void resign(T obj) {
        //只会执行一个：向上或者向下
        heapInsert(indexMap.get(obj));
        heapify(indexMap.get(obj));
    }

    // 获取所有,请返回堆上的所有元素
    public List<T> getAllElements() {
        List<T> ans = new ArrayList<>();
        for (T c : heap) {
            ans.add(c);
        }
        return ans;
    }

    //根据index向上调整
    private void heapInsert(int index) {
        //根据比较器比大小
        //好的放前面，坏的放后面
        //父节点：(index - 1) / 2
        while (comp.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
            //子节点放前面，父子节点交换
            swap(index, (index - 1) / 2);
            //index移动到父节点
            index = (index - 1) / 2;
        }
    }

    //根据index向下移动
    private void heapify(int index) {
        //左孩子
        int left = index * 2 + 1;
        //判断是否越界
        while (left < heapSize) {//有左孩子
            //右孩子和左孩子比较找到最好的
            int best = left + 1 < heapSize && comp.compare(heap.get(left + 1), heap.get(left)) < 0 ? (left + 1) : left;
            //好孩子和父节点比较哪个好
            best = comp.compare(heap.get(best), heap.get(index)) < 0 ? best : index;
            if (best == index) { //好的是父节点就退出循环
                break;
            }
            //交换好孩子和父节点
            swap(best, index);
            //index移动到好孩子位置
            index = best;
            //计算左孩子
            left = index * 2 + 1;

        }
    }

    //交换堆中对象和反向索引表索引也交换
    private void swap(int i, int j) {
        T o1 = heap.get(i);
        T o2 = heap.get(j);
        //交换堆中对象
        heap.set(i, o2);
        heap.set(j, o1);
        //交换对象索引,交换反向索引表中索引
        indexMap.put(o2, i);
        indexMap.put(o1, j);
    }


    //自定义比较器：从小到大
    public static class MyComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 - o2;
        }
    }


    public static void main(String[] args) {

        System.out.println("基本功能 test begin");
        int value = 1000;
        int testTimes = 1000000;
        HeapGreater<Integer> heap = new HeapGreater<>(new MyComparator());
        PriorityQueue<Integer> test = new PriorityQueue<>(new MyComparator());
        for (int i = 0; i < testTimes; i++) {
            int curValue = (int) (Math.random() * value);
            heap.push(curValue);
            test.add(curValue);
            if (Math.random() < 0.5) {
                if (!heap.isEmpty()) {
                    int heapPop = heap.peek();
                    int testPoll = test.peek();
                    if (heapPop != testPoll) {
                        System.out.println("Oops!");
                        System.out.println("heapPop:" + heapPop + ", testPoll:" + testPoll);
                        break;
                    }
//                    if(!(heap.pop().equals(test.poll()))){
//                        System.out.println("Oops!");
//                        System.out.println("heapPop:" + heapPop + ", testPoll:" + testPoll);
//                        break;
//                    }
                    heapPop = heap.pop();
                    testPoll = test.poll();
                    if (heapPop != testPoll) {
                        System.out.println("Oops!");
                        System.out.println("heapPop:" + heapPop + ", testPoll:" + testPoll);
                        break;
                    }
                }
            }
        }
        System.out.println("基本功能 test finish!");


        System.out.println("扩展方法 test begin");

        //加强
        int[] arr1 = {16, 12, 15, 8, 19, 13, 26, 37};
        //测试
        int[] arr2 = {16, 12, 15, 19, 13, 26, 37};
        //加入加强堆
        HeapGreater<Integer> h1 = new HeapGreater<>(new MyComparator());
        for (int i = 0; i < arr1.length; i++) {
            h1.push(arr1[i]);
        }
        h1.remove(8);
        List<Integer> list = h1.getAllElements();
        for (Integer num : list) {
            System.out.print(num + ", ");
        }
        System.out.println();

        //测试堆
        PriorityQueue<Integer> t1 = new PriorityQueue<>(new MyComparator());
        for (int i = 0; i < arr2.length; i++) {
            t1.add(arr2[i]);
        }
        Iterator<Integer> iterator = t1.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + ", ");
        }
        System.out.println();

        if (h1.peek() == t1.peek()) {
            System.out.println("ok");
        } else {
            System.out.println("error");
        }
        System.out.println("扩展方法 test end");

    }
}
